/*
https://leetcode.cn/problems/longest-univalue-path/description/
最长同值路径 
 */

-------------------------------------------------------------------
class Solution {
public:
    // cnt1 存储从当前节点出发向一个方向延伸的最长相同值路径长度
    unordered_map<TreeNode*, int> cnt1;
    // cnt2 存储通过当前节点连接左右子树的最长相同值路径长度
    unordered_map<TreeNode*, int> cnt2;
    // maxPath 用于记录全局的最大路径长度
    int maxPath = 0;

    /**
     * 后序遍历计算每个节点的最长相同值路径长度。
     *
     * @param root 当前处理的树节点
     */
    void getPostOrderCnt(TreeNode* root) {
        if (root) {
            // 先递归处理左右子树
            getPostOrderCnt(root->left);
            getPostOrderCnt(root->right);

            // 初始化候选路径长度为0
            int cand1 = 0, cand2 = 0;

            // 如果左子节点存在且与当前节点值相同，则更新左方向的路径长度
            if (root->left && root->left->val == root->val) {
                cand1 = cnt1[root->left] + 1;
            }

            // 如果右子节点存在且与当前节点值相同，则更新右方向的路径长度
            if (root->right && root->right->val == root->val) {
                cand2 = cnt1[root->right] + 1;
            }

            // 更新cnt1[root]为单侧最大路径长度
            cnt1[root] = max(cand1, cand2);

            // 更新cnt2[root]为通过当前节点连接左右子树的路径长度
            cnt2[root] = cand1 + cand2;

            // 更新全局最大路径长度
            maxPath = max(maxPath, max(cnt1[root], cnt2[root]));
        }
    }

    /**
     * 返回二叉树中最长相同值路径的长度。
     *
     * @param root 树的根节点
     * @return 最长相同值路径的长度
     */
    int longestUnivaluePath(TreeNode* root) {
        getPostOrderCnt(root); // 调用辅助函数计算每个节点的最大路径长度
        return maxPath; // 返回最终结果
    }
};